1. Field of the Invention
The present invention relates to a modular arithmetic, or residue arithmetic, operation system suited for modular arithmetic used in the RSA encryption in a public key cryptosystem, for example, and more particularly, to a modular arithmetic unit which performs efficient residue arithmetic using the Montgomery's algorithm, a modular multiplication arithmetic unit which performs efficient modular multiplication using the residue arithmetic, and a table setup device for setting up a table of multiples for the modular arithmetic.
2. Description of the Related Art
The recent development of computer network systems has rapidly increased opportunities to send and receive digitized information and messages over networks, like database services, electronic mail service, electronic news services and the like. In addition, other information services, such as on-line shopping service, are now being made available. However, it is pointed out that problems arise in connection with these information services in that data on the network is subject to wiretapping, falsification, and illegal access. In wireless network systems employing radio communications in particular, messages are subject to interception and thus measures against this problem are demanded.
To address those problems, an encrypted electronic mail system using cryptography and a user authentication system have been proposed, which are now being introduced into various network systems. In this respect, encryption technology can be said to be one of technologies that are essential to computer network systems.
The encryption technology includes a public key cryptosystem suitable for digital signature, i.e., user authentication. The public key cryptosystem involves a great amount of computation for encryption and decryption. Thus, a high-speed public key cryptosystem is desired. So far, various efficient algorithms have been announced.
The cryptosystems can be roughly classified into two: secret key cryptosystem and public key cryptosystem.
In the secret key cryptosystem, the sender and the recipient use the same encryption key for encrypted communications. That is, in the secret key cryptosystem, the sender enciphers a message (plaintext) using the secret encryption key and the recipient deciphers the encrypted message (ciphertext) using the same encryption key to obtain the original message.
In the public key cryptosystem, on the other hand, the sender enciphers a message using the recipient's encryption key that is made public and the recipient deciphers the encrypted message from the sender using his secret decryption key. That is, in the public key cryptosystem, the public key is used for encryption and the secret key is used for deciphering the message encrypted using the public key. Only the secret key is allowed to decipher a message encrypted by the public key.
In the secret key cryptosystem, each subscriber or user has to hold as many secret keys as there are subscribers with whom he or she communicates. A network having n subscribers would require a total of n(n-1)/2 keys. A problem arises in connection with this system in that each subscriber has to deliver a secret key to a separate subscriber with whom he or she communicates for the first time. To remedy this problem, an approach taken by a large-scale network system is such that there is installed a key management center which holds only secret keys each used for communications between the center and respective individual subscribers, and for communication with a subscriber a sender gets from the center a secret key for the recipient. In this case, the total number of secret keys would be n.
In the public key cryptosystem, on the other hand, each subscriber has to hold only his or her own secret key. The total number of secret keys required is n in the case of an n-subscriber network system. A sender has only to deliver his or her public key to a recipient with whom the sender communicates for the first time. Specifically, there is installed a key management center equipped with a public directory into which n users' public keys are entered. For communication each sender has only to get the public key of a recipient from the center. In this case, the center has only to prevent the public keys from being falsified and does not have to hold the keys in secret. The public key system needs a larger number of bits for each key than the secret key system. Thus, the size of a file for storing the keys increases.
For authentication, in the secret key cryptosystem, the sender compresses a message with the secret key. It is sent combined with that message. The recipient likewise compresses for comparison. However, since the sender and the recipient use the same key, the recipient will be able to forge authentication data.
In contrast, the public key cryptosystem has a feature that it is only the person in question that is allowed to encrypt a message using the secret key. The sender compresses a message and then encrypts it using the secret key. The compressed and encrypted message is sent combined with that message. The recipient deciphers the combined data using the public key of the sender and then compresses it for comparison. In this case, the recipient will not be able to commit an injustice.
Thus, the public key cryptographic technique can be said to be essential to the authentication. However, the public key cryptosystem has a major drawback that it requires a great amount of calculation for encryption and decryption. Therefore, both of the systems are often used in combination. That is, in general, the fast secret key cryptosystem is used for encrypting messages and the public key cryptosystem is used for authentication.
Of most importance among the public key systems is the RSA encryption technique using the RSA algorithm that was devised by Rivest, Shamir and Adlman in 1977. The basic principle of the RSA encryption is as follows.
&lt;RSA basic algorithm&gt;
In an encryption key (e, N) and the corresponding decryption key (d, N), e and N are public keys and d a secret key. Let M be an original message or plaintext and C be a ciphertext. Then, the algorithms for encryption E and decryption D are represented by
C=E(M)=M.sup.e mod N PA1 M=D(C)=C.sup.d mod N PA1 d.e=1 mod LCM {(p-1), (q-1)} PA1 N=p.q PA1 LCM=lowest common multiple PA1 p, q=large prime numbers PA1 m=(T mod R)N' mod R PA1 t=(T+mN)/R PA1 if t&lt;N then return t else return t-N PA1 i=0 to n-1 PA1 m'=T.sub.0 N' mod b PA1 T=T+m'N PA1 t=T/b next
where
Normally, each of e, d, N and M is a large integer consisting of about 512 bits. Even using fast modular exponentiation, modular multiplication and modular arithmetic must be performed, on average, 770 times in an RSA operation. For modular arithmetic in particular, many efficient arithmetic techniques, such as an approximation technique, a residue table technique, the Montgomery's algorithm, etc., have been proposed.
In order to efficiently process an algorithm for modular exponentiation that is most commonly used in the public key cryptosystems represented by the RSA cryptosystem, it is required to speed up modular arithmetic in an RSA operation.
The Montgomery's algorithm ("Modular Multiplication Without Trial Division", Peter L. Montgomery, Mathematics of Computation, Volume 44, Number 170, April 1985 pp. 519 to 528), which is an technique to speed up modular arithmetic, will be described below.
&lt;Montgomery's algorithm&gt;
The Montgomery's algorithm is an algorithm which allows modular arithmetic without division by modulo N by using that, by the use of modulo N (N&gt;1) and a radix R (R&gt;N) that is coprime to N, computation of TR.sup.-1 mod N from T is performed only by division by R. Here, N, N', R, R.sup.-1 are each an integer. T is 0.ltoreq.T&lt;RN. R.sup.-1 is the reciprocal of the radix R, modulo N (RR.sup.-1 mod N=1), satisfying RR.sup.-1 -NN'=1 (0.ltoreq.R.sup.-1 &lt;N, 0.ltoreq.N'&lt;R).
When the radix R is selected to be a power of 2, the division by R can be replaced by simple shift operations, permitting high-speed computation T.fwdarw.TR.sup.-1 mod N.
Next, algorithm REDC(T) for T.fwdarw.TR.sup.-1 mod N is indicated as "Algorithm 1". In "Algorithm 1", (T+mN)/R is divisible exactly.
&lt;Algorithm 1&gt;
The algorithm REDC(T) for T.fwdarw.TR.sup.-1 mod N is represented as follows:
That is, ##EQU1##
In a single REDC operation, TR.sup.-1 mod N is merely obtained, not T mod N. In order to obtain T mod N, it is thus required to perform an REDC operation again using the product of REDC(T) and R.sup.2 mod N obtained in advance as follows: ##EQU2## In this way, T mod N can be obtained. &lt;Extension of REDC to multiprecision arithmetic&gt;
Next, the REDC arithmetic algorithm is extended to multiprecision arithmetic where the modulo N or the radix R is multilength, i.e., multiprecision.
When the modulo N or the radix R is multiprecision, computations of (T mod R)N' and mN in the REDC arithmetic involve processing of multiprecision.times.multiprecision, which requires of a general-purpose computer a very great amount of computation and a very large amount of processing time. "Algorithm 2" is then shown below which allows this part of arithmetic to be performed by processing of multiprecision.times.single-precision.
&lt;Algorithm 2&gt;
The algorithm which permits an extension of the REDC arithmetic to multiprecision is shown as follows.
Assume that T is a base b number and T=(T.sub.2n-1 T.sub.2n-2 . . . T.sub.0).sub.b, R=b.sup.n, b=2.sup.k. When the following arithmetic is performed repeatedly for i=0 to n-1, TR.sup.-1 mod N can be obtained in the same manner as the single-length, i.e., single-precision arithmetic.
for
which involves the use of mutual division of extended Euclid's algorithm, requires a larger amount of time than R.sup.2 mod N to process.